//多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生
//成多级数据结构，如下面的示例所示。
//
// 给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
//输出：[1,2,3,7,8,11,12,9,10,4,5,6]
//解释：
//
//输入的多级列表如下图所示：
//
//
//
//扁平化后的链表如下图：
//
//
//
//
// 示例 2：
//
//
//输入：head = [1,2,null,3]
//输出：[1,3,2]
//解释：
//
//输入的多级列表如下图所示：
//
//  1---2---NULL
//  |
//  3---NULL
//
//
// 示例 3：
//
//
//输入：head = []
//输出：[]
//
//
//
//
// 如何表示测试用例中的多级链表？
//
// 以 示例 1 为例：
//
//
// 1---2---3---4---5---6--NULL
//         |
//         7---8---9---10--NULL
//             |
//             11--12--NULL
//
// 序列化其中的每一级之后：
//
//
//[1,2,3,4,5,6,null]
//[7,8,9,10,null]
//[11,12,null]
//
//
// 为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
//
//
//[1,2,3,4,5,6,null]
//[null,null,7,8,9,10,null]
//[null,11,12,null]
//
//
// 合并所有序列化结果，并去除末尾的 null 。
//
//
//[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
//
//
//
// 提示：
//
//
// 节点数目不超过 1000
// 1 <= Node.val <= 10^5
//
//
//
//
//
// 注意：本题与主站 430 题相同： https://leetcode-cn.com/problems/flatten-a-multilevel-
//doubly-linked-list/
//
// Related Topics 深度优先搜索 链表 双向链表 👍 74 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     prev: Node | null
 *     next: Node | null
 *     child: Node | null
 *     constructor(val?: number, prev? : Node, next? : Node, child? : Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.prev = (prev===undefined ? null : prev);
 *         this.next = (next===undefined ? null : next);
 *         this.child = (child===undefined ? null : child);
 *     }
 * }
 */

function flatten(head: Node | null): Node | null {

    /**
     * @param {Node} head
     * @return {Node}
     */
        //? 展平以head为头节点的链表之后返回链表的尾节点
    const flattenGetTail = (head) => {
            let node = head;
            let tail = null;
            //? 逐一扫描链表的节点
            while (node) {
                let next = node.next;
                //? 如果节点node有子链表，由于子链表也可能有嵌套的子链表
                if (node.child) {
                    let child = node.child;
                    //? 递归调用flattenGetTail函数展平子链表
                    let childTail = flattenGetTail(node.child);
                    //? 子链表展平之后的头节点是child，尾节点是childTail
                    node.child = null;
                    //? 当展平的子链表插入节点node和它的下一下节点next之间（也就是把展平的子链表的头节点child插入节点node之后，并将尾节点childTail插入节点next之前）
                    node.next = child;
                    child.prev = node;
                    childTail.next = next;
                    if (next) {
                        next.prev = childTail;
                    }
                    tail = childTail;
                } else {
                    tail = node;
                }
                node = next;
            }
            return tail;
        };
    flattenGetTail(head);
    return head;


};
//leetcode submit region end(Prohibit modification and deletion)
